package com.markus.code.二叉树.leetcode;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/10 20:09
 * todo: 二叉树中的最大路径和
 */
public class LeetCode_124 {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val = val;
        }
    }
    public static class Info{
        public int maxPathSum;//最大路径和
        public int pathSum;//含当前节点的路径和
        public Info(int maxPathSum,int pathSum){
            this.maxPathSum = maxPathSum;
            this.pathSum = pathSum;
        }
    }
    public int maxPathSum(TreeNode root) {
        return process(root).maxPathSum;
    }
    private Info process(TreeNode x){
        if (x == null){
            return null;
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int maxPathSum = Integer.MIN_VALUE;
        int pathSum = Integer.MIN_VALUE;
        //最大路径和与当前x节点无关;
        maxPathSum = Math.max(leftInfo==null?Integer.MIN_VALUE:leftInfo.maxPathSum,rightInfo==null?Integer.MIN_VALUE:rightInfo.maxPathSum);
        //最大路径和与当前x节点有关;
        int sonSum = Math.max(leftInfo==null?Integer.MIN_VALUE:leftInfo.pathSum+x.val,rightInfo==null?Integer.MIN_VALUE:rightInfo.pathSum+x.val);
        pathSum = Math.max(sonSum,x.val);

        int leftRightPathSum = x.val;
        if (leftInfo != null){
            leftRightPathSum += leftInfo.pathSum;
        }
        if (rightInfo != null){
            leftRightPathSum += rightInfo.pathSum;
        }
        maxPathSum = Math.max(Math.max(leftRightPathSum,pathSum),maxPathSum);
        return new Info(maxPathSum,pathSum);
    }

    public static void main(String[] args) {
        LeetCode_124 demo = new LeetCode_124();
//        TreeNode A = new TreeNode(1);
//        A.left = new TreeNode(2);
//        A.right = new TreeNode(3);
//        System.out.println(demo.maxPathSum(A));
//        TreeNode A = new TreeNode(-10);
//        A .left = new TreeNode(9);
//        A.right = new TreeNode(20);
//        A.right.left = new TreeNode(15);
//        A.right.right = new TreeNode(7);
        TreeNode A = new TreeNode(9);
        A.left = new TreeNode(6);
        A.right = new TreeNode(-3);
        A.right.left = new TreeNode(-6);
        A.right.right = new TreeNode(2);
        A.right.right.left = new TreeNode(2);
        A.right.right.left.left = new TreeNode(-6);
        A.right.right.left.right = new TreeNode(-6);
        A.right.right.left.left.left = new TreeNode(-6);

        System.out.println(demo.maxPathSum(A));
    }
}
